package com.sparsearr.datastructures.ztr.linkedlist;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;

/**
 * @Author: ZhaoTR
 * @Date: Created in 2025/4/12 21:16
 * @Description: 环形链表
 * @Version: 1.0
 */

public class Josepfu {
    private static final Logger logger = LogManager.getLogger(Josepfu.class);

    public static void main(String[] args) {
        // 创建环形链表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        // 添加小孩节点5个
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoy();

        // 出圈的顺序
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

// 创建环形链表并完成遍历
class CircleSingleLinkedList {
    // 创建一个first节点，当前没有编号
    private Boy first = null;

    // 添加小孩节点，构建成一个环形链表
    public void addBoy(int nums) {
        // nums 做一个数据校验
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        // 赋值指针，帮助构建环形链表
        Boy curBoy = null;
        // 使用for来创建环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号创建节点
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                // 构成环
                first.setNext(first);
                // 指向第一个节点
                curBoy = first;
            } else {
                // 将当前节点指向新节点
                curBoy.setNext(boy);
                // 新节点指向头节点，形成环
                boy.setNext(first);
                // 更新辅助指针
                curBoy = boy;
            }
        }
    }

    // 遍历当前环形链表
    public void showBoy() {
        // 判断链表是否为空
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        // 辅助指针，帮助遍历
        // first 不能动，创建一个辅助指针完成遍历
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的编号%d \n", curBoy.getNo());
            // 遍历到链表最后，结束
            if (curBoy.getNext() == first) {
                break;
            }
            // 将辅助指针后移
            curBoy = curBoy.getNext();
        }
    }

    // 根据用户的输入，计算出小孩出圈的顺序

    /**
     * @param startNo  表示从第几个节点开始数数
     * @param countNum 表示数几下
     * @param nums     表示最初有多少个节点在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // 先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入！");
            return;
        }

        // 创建辅助指针，帮助完成遍历
        Boy helper = first;

        // 让 helper 指向环形链表的最后一个节点
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }

        // 将 first 和 helper 移动到起始位置
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 开始循环操作，直到圈中只剩下一个节点
        while (true) {
            // 如果只剩下一个节点，退出循环
            if (helper == first) {
                break;
            }

            // 数 `countNum` 个节点
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }

            // 输出出圈的小孩编号
            System.out.printf("小孩出圈：%d\n", first.getNo());

            // 移除当前节点
            first = first.getNext();
            helper.setNext(first);
        }

        // 输出最后留在圈中的小孩编号
        System.out.printf("最后留在圈中的小孩编号：%d\n", helper.getNo());
    }
}

// 创建一个Boy类，表示一个节点
class Boy {
    // 编号
    private int no;

    // 指向下一个节点,默认为null
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
